
//struct Node* deepCopy(struct Node* head) {
//    if (head == NULL) 
//    {
//        return NULL;
//    }
//    struct HashTable* tmp;
//    HASH_FIND_PTR(cachedNode, &head, tmp);
//    if (tmp == NULL) 
//    {
//        struct Node* headNew = malloc(sizeof(struct Node));
//        headNew->val = head->val;
//        tmp = malloc(sizeof(struct HashTable));
//        tmp->key = head, tmp->val = headNew;
//        HASH_ADD_PTR(cachedNode, key, tmp);
//        headNew->next = deepCopy(head->next);
//        headNew->random = deepCopy(head->random);
//    }
//    return tmp->val;
//}
//
//struct Node* copyRandomList(struct Node* head) 
//{
//    cachedNode = NULL;
//    return deepCopy(head);
//}


//struct Node* copyRandomList(struct Node* head) {
//    if (head == NULL) 
//    {
//        return NULL;
//    }
//
//    for (struct Node* node = head; node != NULL; node = node->next->next) 
//    {
//        struct Node* nodeNew = malloc(sizeof(struct Node));
//        nodeNew->val = node->val;
//        nodeNew->next = node->next;
//        node->next = nodeNew;
//    }
//    for (struct Node* node = head; node != NULL; node = node->next->next) 
//    {
//        struct Node* nodeNew = node->next;
//        nodeNew->random = (node->random != NULL) ? node->random->next : NULL;
//    }
//    struct Node* headNew = head->next;
//    for (struct Node* node = head; node != NULL; node = node->next) 
//    {
//        struct Node* nodeNew = node->next;
//        node->next = node->next->next;
//        nodeNew->next = (nodeNew->next != NULL) ? nodeNew->next->next : NULL;
//    }
//    return headNew;
//}






//char pairs(char a) 
//{
//    if (a == '}') return '{';
//    if (a == ']') return '[';
//    if (a == ')') return '(';
//    return 0;
//}
//
//bool isValid(char* s) 
//{
//    int n = strlen(s);
//    if (n % 2 == 1) 
//    {
//        return false;
//    }
//    int stk[n + 1], top = 0;
//    for (int i = 0; i < n; i++) 
//    {
//        char ch = pairs(s[i]);
//        if (ch) {
//            if (top == 0 || stk[top - 1] != ch) 
//            {
//                return false;
//            }
//            top--;
//        }
//        else 
//        {
//            stk[top++] = s[i];
//        }
//    }
//    return top == 0;
//}





//#define LEN 20
//typedef struct queue
//{
//    int* data;
//    int head;
//    int rear;
//    int size;
//} Queue;
//
//typedef struct 
//{
//    Queue* queue1, * queue2;
//} MyStack;
//
//Queue* initQueue(int k) 
//{
//    Queue* obj = (Queue*)malloc(sizeof(Queue));
//    obj->data = (int*)malloc(k * sizeof(int));
//    obj->head = -1;
//    obj->rear = -1;
//    obj->size = k;
//    return obj;
//}
//
//void enQueue(Queue* obj, int e)
//{
//    if (obj->head == -1) 
//    {
//        obj->head = 0;
//    }
//    obj->rear = (obj->rear + 1) % obj->size;
//    obj->data[obj->rear] = e;
//}
//
//int deQueue(Queue* obj) 
//{
//    int a = obj->data[obj->head];
//    if (obj->head == obj->rear)
//    {
//        obj->rear = -1;
//        obj->head = -1;
//        return a;
//    }
//    obj->head = (obj->head + 1) % obj->size;
//    return a;
//}
//
//int isEmpty(Queue* obj) 
//{
//    return obj->head == -1;
//}
//
//MyStack* myStackCreate() 
//{
//    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
//    obj->queue1 = initQueue(LEN);
//    obj->queue2 = initQueue(LEN);
//    return obj;
//}
//
//void myStackPush(MyStack* obj, int x) 
//{
//    if (isEmpty(obj->queue1)) 
//    {
//        enQueue(obj->queue2, x);
//    }
//    else 
//    {
//        enQueue(obj->queue1, x);
//    }
//}
//
//int myStackPop(MyStack* obj)
//{
//    if (isEmpty(obj->queue1)) 
//    {
//        while (obj->queue2->head != obj->queue2->rear) 
//        {
//            enQueue(obj->queue1, deQueue(obj->queue2));
//        }
//        return deQueue(obj->queue2);
//    }
//    while (obj->queue1->head != obj->queue1->rear)
//    {
//        enQueue(obj->queue2, deQueue(obj->queue1));
//    }
//    return deQueue(obj->queue1);
//}
//
//int myStackTop(MyStack* obj) 
//{
//    if (isEmpty(obj->queue1)) 
//    {
//        return obj->queue2->data[obj->queue2->rear];
//    }
//    return obj->queue1->data[obj->queue1->rear];
//}
//
//bool myStackEmpty(MyStack* obj) 
//{
//    if (obj->queue1->head == -1 && obj->queue2->head == -1) 
//    {
//        return true;
//    }
//    return false;
//}
//
//void myStackFree(MyStack* obj)  
//{
//    free(obj->queue1->data);
//    obj->queue1->data = NULL;
//    free(obj->queue1);
//    obj->queue1 = NULL;
//    free(obj->queue2->data);
//    obj->queue2->data = NULL;
//    free(obj->queue2);
//    obj->queue2 = NULL;
//    free(obj);
//    obj = NULL;
//}




//typedef struct tagListNode 
//{
//    struct tagListNode* next;
//    int val;
//} ListNode;
//
//typedef struct
//{
//    ListNode* top;
//} MyStack;
//
//MyStack* myStackCreate() 
//{
//    MyStack* stk = calloc(1, sizeof(MyStack));
//    return stk;
//}
//
//void myStackPush(MyStack* obj, int x)
//{
//    ListNode* node = malloc(sizeof(ListNode));
//    node->val = x;
//    node->next = obj->top;
//    obj->top = node;
//}
//
//int myStackPop(MyStack* obj)
//{
//    ListNode* node = obj->top;
//    int val = node->val;
//    obj->top = node->next;
//    free(node);
//
//    return val;
//}
//
//int myStackTop(MyStack* obj) 
//{
//    return obj->top->val;
//}
//
//bool myStackEmpty(MyStack* obj)
//{
//    return (obj->top == NULL);
//}
//
//void myStackFree(MyStack* obj) 
//{
//    while (obj->top != NULL) 
//    {
//        ListNode* node = obj->top;
//        obj->top = obj->top->next;
//        free(node);
//    }
//    free(obj);
//}



typedef struct 
{
    int* stk;
    int stkSize;
    int stkCapacity;
} Stack;

Stack* stackCreate(int cpacity) 
{
    Stack* ret = malloc(sizeof(Stack));
    ret->stk = malloc(sizeof(int) * cpacity);
    ret->stkSize = 0;
    ret->stkCapacity = cpacity;
    return ret;
}

void stackPush(Stack* obj, int x) 
{
    obj->stk[obj->stkSize++] = x;
}

void stackPop(Stack* obj)
{
    obj->stkSize--;
}

int stackTop(Stack* obj) 
{
    return obj->stk[obj->stkSize - 1];
}

bool stackEmpty(Stack* obj)
{
    return obj->stkSize == 0;
}

void stackFree(Stack* obj)
{
    free(obj->stk);
}

typedef struct 
{
    Stack* inStack;
    Stack* outStack;
} MyQueue;

MyQueue* myQueueCreate()
{
    MyQueue* ret = malloc(sizeof(MyQueue));
    ret->inStack = stackCreate(100);
    ret->outStack = stackCreate(100);
    return ret;
}

void in2out(MyQueue* obj)
{
    while (!stackEmpty(obj->inStack))
    {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}

void myQueuePush(MyQueue* obj, int x) 
{
    stackPush(obj->inStack, x);
}

int myQueuePop(MyQueue* obj)
{
    if (stackEmpty(obj->outStack)) 
    {
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}

int myQueuePeek(MyQueue* obj)
{
    if (stackEmpty(obj->outStack))
    {
        in2out(obj);
    }
    return stackTop(obj->outStack);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}

void myQueueFree(MyQueue* obj)
{
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}

